package Midium;

import java.util.*;

// 435. 无重叠区间
// 面试官要求用dp，然后没想出来，于是面试挂了。
public class Solution435 {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) return 0;

        Queue<int[]> queue = new PriorityQueue(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] == o2[1] ? o2[0] - o1[0] : o1[1] - o2[1];
            }
        });
        for (int i = 0; i < intervals.length; i++) {
            queue.offer(intervals[i]);
        }
        int[] first = queue.poll();
        int curEnd = first[1];
        int result = 0;
        while (!queue.isEmpty()) {
            int[] next = queue.poll();
            if(next[0] < curEnd){
                result++;
                continue;
            }else {
                curEnd = next[1];
            }
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(new Solution435().eraseOverlapIntervals(new int[][]{{1,2},{2,3},{3,4},{1,3}}));
    }
}
